#ifndef _basic_queue_impl_hpp_
#define _basic_queue_impl_hpp_

/** \file basic_queue_impl.hpp
 *  \author Adrian Schweizer
 *  \created  $Sa 18 Aug 03:48:01 pm CEST 2007 schwadri@SchwadriComp.local$
 *  \modified $So 19 Aug 12:39:05 pm CEST 2007 schwadri@SchwadriComp.local$
 *  \todo
 *  - check all routines for exception safety
 *  - make iterators fully STL compliant
 */

#include <boost/type_traits/has_trivial_constructor.hpp>

namespace core {

    namespace detail {
        template<class T,class A>
            class   basic_queue_impl;
        //FIXME: const_iterator and normal iterator not working together properly
        template<class Pointer,class Reference,class QueueImpl>
            class queue_iterator
            {
            public:
                typedef queue_iterator<Pointer,Reference,QueueImpl>     my_type;
                typedef QueueImpl                                       container_type;
                typedef Pointer                                         pointer;
                typedef Reference                                       reference;

                inline bool operator==(const my_type& o)
                {
                    return o.m_p == m_p;
                }

                template<class P, class R, class Q>
                    inline bool operator==(const queue_iterator<P,R,Q>& o)
                    {
                        return o.m_p == m_p;
                    }

                inline bool operator!=(const my_type& o)
                {
                    return !operator==(o);
                }

                template<class P, class R, class Q>
                    inline bool operator!=(const queue_iterator<P,R,Q>& o)
                    {
                        return !operator==(o);
                    }

                inline reference   operator*()
                {
                    return *(m_container.m_storage_begin+m_p);
                }
                inline pointer   operator->()
                {
                    return (m_container.m_storage_begin+m_p);
                }
                inline void operator++()
                {
                    ++m_p;
                    m_p %= m_container.internal_capacity();
                }
                inline void operator--()
                {
                    --m_p;
                    m_p %= m_container.internal_capacity();
                }

                template<class P, class R, class Q>
                    queue_iterator(const queue_iterator<P,R,Q>& oiter)
                    :   m_container(oiter.m_container),
                        m_p(oiter.m_p)
                    {

                    }

                friend class basic_queue_impl<typename container_type::value_type,typename container_type::allocator_type>;
            private:
                queue_iterator(container_type& queue,int p)
                :   m_container(queue),
                    m_p(p)
                { }
                container_type&     m_container;
                int                 m_p;
            };

        template<class T, class Allocator >
            class   basic_queue_impl
            {
            public:
                typedef basic_queue_impl<T,Allocator>                           my_type;
                typedef Allocator                                               allocator_type;
                typedef typename allocator_type::size_type                      size_type;
                typedef typename allocator_type::pointer                        pointer;
                typedef typename allocator_type::const_pointer                  const_pointer;
                typedef typename allocator_type::reference                      reference;
                typedef typename allocator_type::const_reference                const_reference;
                typedef typename allocator_type::value_type                     value_type;
                typedef queue_iterator<pointer,reference,my_type>               iterator;
                typedef queue_iterator<const_pointer,
                                        const_reference,const my_type>          const_iterator;

                basic_queue_impl(size_type size)
                :   m_allocator(),
                    m_storage_begin(0),
                    m_storage_end(0),
                    m_begin(0),
                    m_end(0)
                {
                    if(size)
                    {
                        m_storage_begin =   m_allocator.allocate(++size);
                        m_storage_end   =   m_storage_begin + size;
                    }
                }

                basic_queue_impl()
                :   m_allocator(),
                    m_storage_begin(0),
                    m_storage_end(0),
                    m_begin(0),
                    m_end(0)
                { }

                basic_queue_impl(const my_type& other)
                :   m_allocator(other.m_allocator),
                    m_storage_begin(other.m_storage_begin),
                    m_storage_end(other.m_storage_end),
                    m_begin(other.m_begin),
                    m_end(other.m_end)
                {
                    if(other.internal_capacity())
                    {
                        using std::copy;
                        m_storage_begin =   m_allocator.allocate(other.internal_capacity());
                        m_storage_end   =   m_storage_begin+other.internal_capacity();

                        copy(other.m_storage_begin,other.m_storage_end,m_storage_begin);
                    }
                }

                ~basic_queue_impl()
                {
                    if(m_storage_begin)
                    {
                        using boost::has_trivial_constructor;
                        //first destroy all elements
                        if(!has_trivial_constructor<value_type>::value && !empty())
                            destroy(m_begin,m_end); // this can't throw

                        //and free the allocated space
                        m_allocator.deallocate(m_storage_begin,internal_capacity());
                    }
                }

                inline size_type capacity() const
                {
                    return internal_capacity()-1;
                }

                inline size_type max_size() const
                {
                    using std::numeric_limits;
                    return numeric_limits<size_type>::max();
                }

                /** \internal
                 *  \brief exception safe swap
                 *  FIXME: atm swapping of two containers with the same element type but a different allocator
                 *  is not possible.
                 */
                void swap(my_type& o)
                {
                    using std::swap;
                    swap(m_allocator,o.m_allocator);
                    swap(m_storage_begin,o.m_storage_begin);
                    swap(m_storage_end,o.m_storage_end);
                    swap(m_begin,o.m_begin);
                    swap(m_end,o.m_end);
                }

                inline size_type size() const
                {
                    if(internal_capacity())
                        return (internal_capacity() - m_begin+m_end)%internal_capacity();
                    else
                        return 0;
                }

                inline bool full() const
                {
                    if(internal_capacity())
                        return ((m_end+1)%internal_capacity()) == m_begin || m_storage_begin==0;
                    else
                        return  true;
                }

                inline bool empty() const
                {
                    return m_begin == m_end;
                }

                void    clear()
                {
                    using boost::has_trivial_constructor;
                    //destroy all elements
                    //unfortunately on most compilers this seems to be true for every struct/class even if there is a trivial ctor/dtor
                    //thus we still iterate over the whole range of elements basically doing nothing
                    if(!has_trivial_constructor<value_type>::value)
                        destroy(m_begin,m_end); //this can't throw

                    //reset indices
                    m_begin =   m_end   =   0;
                }

                /** \internal
                 *  \par FIXME
                 *  -   if the allocator throws we have to catch the exception in order to provide
                 *      STL compatible behaviour
                 *  -   In its current implementation we are NOT exception safe! An exception thrown
                 *      during the copy algorithm will leave the internal buffer unchanged but any 
                 *      elements that have already been copied will not be destructed properly
                 */
                void reserve(size_type  sz)
                {
                    using std::copy;

                    //waste one byte for the end index
                    ++sz;

                    //don't do anything if we have already enough capacity
                    if(sz<= internal_capacity())
                        return;

                    pointer m_new;
                    try {
                        m_new   =   m_allocator.allocate(sz);
                    }
                    catch(...)
                    {
                        //catch exception for STL compatibility
                        return;
                    }

                    if(empty())
                    {
                        if(m_storage_begin)
                        {
                            m_allocator.deallocate(m_storage_begin,internal_capacity());
                        }
                        m_storage_begin =   m_new;
                        m_storage_end   =   m_new   + sz;
                        m_begin =   m_end   =   0;
                    }
                    else
                    {
                        try {
                            if(m_begin<m_end)
                            {
                                copy(m_storage_begin+m_begin,m_storage_begin+m_end,m_new);
                                m_end   =   size();
                                m_begin =   0;
                            }
                            else
                            {
                                copy(m_begin+m_storage_begin,m_storage_end,m_new);
                                if(m_end)
                                    copy(m_storage_begin,m_storage_begin+m_end,m_new + (internal_capacity() - m_begin));
                                m_end   =    size();
                                m_begin =   0;
                            }

                            //now do the stuff that doesn't throw
                            m_allocator.deallocate(m_storage_begin,internal_capacity());
                            m_storage_begin =   m_new;
                            m_storage_end   =   m_new   + sz;
                        }
                        catch(...)
                        {
                            //during copy an exception was thrown
                            //FIXME:roll back copy?

                            //deallocated recently allocated space
                            m_allocator.deallocate(m_new,sz);
                            //rethrow the exception
                            throw;
                        }
                    }
                }

                void resize(size_type size, const_reference value)
                {
                    reserve(size);
                    size_type i=m_end;
                    m_end +=size;
                    m_end %=internal_capacity();
                    for(;i!=m_end;i=(++i)%internal_capacity())
                        construct(i+m_storage_begin,value);

                }

                reference push(const_reference value)
                {
                    if(full())
                    {
                        reserve(size()+1);
                    }
                    reference val_ref   =   *(m_end+m_storage_begin);
                    //val_ref = value;
                    construct(m_end+m_storage_begin,value);
                    ++m_end;
                    m_end %=internal_capacity();
                    return val_ref;
                }

                void pop()
                {
                    if(empty())
                        return;
                    destroy(m_begin+m_storage_begin);
                    ++m_begin;
                    m_begin%=internal_capacity();
                }

                void push_back(const_reference value)
                {
                    push(value);
                }
                void pop_front()
                {
                    pop();
                }
                inline const_reference front() const   { return *(m_storage_begin+m_begin); }
                inline reference       front()         { return *(m_storage_begin+m_begin); }

                inline const_reference  operator[](size_type index) const   { return *(m_storage_begin+((internal_capacity()+m_begin+index)%internal_capacity())); }
                inline reference        operator[](size_type index)         { return *(m_storage_begin+((internal_capacity()+m_begin+index)%internal_capacity())); }
                inline const_reference back() const   { return *(m_storage_begin+((internal_capacity()+m_end-1)%internal_capacity())); }
                inline reference       back()         { return *(m_storage_begin+((internal_capacity()+m_end-1)%internal_capacity())); }

                inline const_iterator begin() const
                {
                    return  const_iterator(*this,m_begin);
                }
                inline const_iterator end() const
                {
                    return  const_iterator(*this,m_end);
                }
                inline iterator begin()
                {
                    return  iterator(*this,m_begin);
                }
                inline iterator end()
                {
                    return  iterator(*this,m_end);
                }

                friend class queue_iterator<pointer,reference,my_type>;
                friend class queue_iterator<const_pointer,const_reference,const my_type>;
            protected:
                /** \internal
                 *  \brief construct a new object at a given address \a p using an initival value
                 */
                template<class T1, class T2>
                    void construct(T1* p,const T2& value)
                    {
                        new (p) T1(value);
                    }

                /** \internal
                 *  \brief destroy the element at address \a p
                 *  \note cannot throw
                 */
                template<class T1>
                    void destroy(T1*  p)
                    {
                        p->~T();
                    }

                /** \internal
                 *  \brief destroy all elements in the iterator range [first,last)
                 *  \note cannot throw
                 */
                template<class FwdIter>
                    void destroy(FwdIter first, FwdIter last)
                    {
                        while(first != last)
                        {
                            destroy(*first);
                            ++first;
                        }
                    }

                /** \internal
                 *  \brief destroy all elements in the index range [first,last)
                 *  \note cannot throw
                 */
                void destroy(int first, int last)
                {
                    for(int i=first;i!=last;i=(++i)%internal_capacity())
                        destroy(m_storage_begin+i);
                }
            private:

                /** \internal
                 *  \brief return the effective capacity of number of elements
                 *
                 *  \note because of the nature of this implementation i have to waste space for one element in order
                 *  to avoid a more complex element index handling. And because of that \a capacity() returns \a internal_capacity() + 1
                 */
                inline size_type internal_capacity() const
                {
                    return m_storage_end-m_storage_begin;
                }
                allocator_type  m_allocator;    ///< the allocator responsible for managing this queue's  memory
                pointer         m_storage_begin;///< pointer to the beginning of the storage area
                pointer         m_storage_end;  ///< pointer to one past the last entry in the storage area
                int             m_begin;        ///< index of the first valid element
                int             m_end;          ///< index of the first free element slot (one past the last valid element)
            };

    } // namespace detail

} // namespace core

#endif // _basic_queue_impl_hpp_
